#include "Search.h"

template<typename T>
int BinarySearch(T* data, int left, int right, const T& val)
{
	if(left > right)
		return -1;
	int middile = (left + right) / 2;
	int compare_result = Compare(data[middile], val);
	if(compare_result == 0)
		return middile;
	else if(compare_result < 0)
		return BinarySearch(data, middile + 1, right, val);
	else
		return BinarySearch(data, left, middile - 1, val);
}
template<typename T>
int BinarySearch(T* data, int size, const T& val)
{
	return BinarySearch(data, 0, size - 1, val);
}


template<typename T>
HashTable<T>::HashTable(int(*hash_func)(const T&, int bins_size))
	: _HashFunc(hash_func)
{
	_HashTable.resize(17);
}

template<typename T>
void HashTable<T>::BuildHashTable(T* data, int size)
{
	_HashTable.clear();
	//bins count = (2^x)+1,where x try to be lesser,but has to make bins count bigger than size 
	_HashTable.resize(std::pow(2, std::floorf(std::log2f(size)) + 1) + 1);
	_DataSize = size;

	for(int i = 0; i < size; ++i)
	{
		int belong_to = _HashFunc(data[i], _HashTable.size());
		_HashTable[belong_to].push_back(data[i]);
	}
}

template<typename T>
void HashTable<T>::PrintHashDistribution()
{
	std::map<int, int> loadfactor_stastic;
	for(auto& each : _HashTable)
	{
		if(loadfactor_stastic.count(each.size()) > 0)
			loadfactor_stastic[each.size()]++;
		else
			loadfactor_stastic[each.size()] = 1;
	}
	for(auto& it : loadfactor_stastic)
	{
		std::cout << "bin size:" << it.first << " bin count:" << it.second << std::endl;
	}
}

template<typename T>
void HashTable<T>::CheckRehash()
{
	if(_DataSize + 1 > _LoadFactor * _HashTable.size())
	{
		clock_t begin = clock();

		std::vector<T> data;
		for(auto& bin : _HashTable)
			for(auto& element : bin)
				data.push_back(element);

		size_t bins_count = _HashTable.size();
		_HashTable.clear();
		_HashTable.resize(2 * bins_count + 1);

		for(auto& element : data)
		{
			int belong_to = _HashFunc(element, _HashTable.size());
			_HashTable[belong_to].push_back(element);
		}

		clock_t end = clock();
		std::cout << "rehash happend... bins count:" << _HashTable.size() << " time:" << end - begin << std::endl;
	}
}

template<typename T>
void HashTable<T>::Add(const T& val)
{
	CheckRehash();

	_DataSize++;
	int belong_to = _HashFunc(val, _HashTable.size());
	_HashTable[belong_to].push_back(val);
}

template<typename T>
void HashTable<T>::Remove(const T& val)
{
	int belong_to = _HashFunc(val, _HashTable.size());
	auto& bin = _HashTable[belong_to];
	auto iterator = std::find(bin.begin(), bin.end(), val);
	if(iterator != bin.end())
		bin.erase(iterator);
	_DataSize--;
}

template<typename T>
bool HashTable<T>::IsExist(const T& val)
{
	int belong_to = _HashFunc(val, _HashTable.size());
	auto& bin = _HashTable[belong_to];
	for(auto& each : bin)
	{
		if(Compare(each, val) == 0)
			return true;
	}
	return false;
}